package com.mdnote.jianzhi_offer.array;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/11
 * @description 剑指 Offer 03. 数组中重复的数字II
 */
public class Offer03II {

    public static void main(String[] args) {
        Offer03II offer03II = new Offer03II();
        int duplication = offer03II.getDuplication(new int[]{0, 1, 2, 3, 2});
        System.out.println(duplication);
    }

    public int getDuplication(int[] arr) {
        // Use binary search
        int left = 0, right = arr.length - 1;
        while (left <= right) {

            int mid = left + ((right - left) >> 1);

            int count = countRepeat(arr, left, mid);
            if (left == right) {
                return count > 1? left : -1;
            }
            if (count > (mid - left + 1)) {
                // 重复的在左边
                right = mid;
            } else if (count < (mid - left + 1)) {
                // 在右边
                left = mid + 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    private int countRepeat(int[] arr, int left, int right) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= left && arr[i] <= right) {
                count++;
            }
        }
        return count;
    }
}
